Many problems in data processing and telecommunications can be solved by intelligently searching through many possible solutions. When the universe of possible solutions, known as the search space, is small, then it is possible to simply perform an exhaustive search—i.e., search the entire search space and find the best solution. In many real-world problems, however, the search space is very large, and therefore finding the best solution via exhaustive search is at best intractable, and at worst impossible. For such problems, it might be necessary to settle for a solution that is “good”, rather than optimal.
A variety of search algorithms have been devised to find good, if not necessarily optimal, solutions to search problems. Many of these search algorithms, though not all, are based on data structures known as search trees. In a search tree algorithm, nodes that correspond to possible solutions are expanded to a set of one or more children (or successor) nodes, and the nodes of the tree are explored in accordance with a particular strategy (e.g., breadth-first search, depth-first search with backtracking, heuristic-guided search, etc.).